package test.node;

public class ListNode {
    int val;
    ListNode next;
    ListNode() {}
    ListNode(int val) { this.val = val; }
    ListNode(int val, ListNode next) { this.val = val; this.next = next; }

    public ListNode reverseListIterative(ListNode head) {
        ListNode prev = null;
        ListNode curr = head;

        while (curr != null) {
            // 1. 保存下一个节点，防止链表断开
            ListNode nextTemp = curr.next;
            // 2. 核心操作：反转指针
            curr.next = prev;
            // 3. 移动 prev 和 curr 指针
            prev = curr;
            curr = nextTemp;
        }
        // 循环结束时，prev 指向原链表的最后一个节点，即新链表的头节点
        return prev;
    }

    public ListNode reverseListRecursive(ListNode head) {
        // 递归基：空链表或只有一个节点，无需反转，直接返回
        if (head == null || head.next == null) {
            return head;
        }

        // 递归反转以 head.next 开头的子链表
        // newHead 始终是反转后链表的头节点（原链表的尾节点）
        ListNode newHead = reverseListRecursive(head.next);

        // 关键步骤：调整指针
        // 此时 head.next 是反转后子链表的最后一个节点
        // 让最后一个节点的 next 指向当前节点 head
        head.next.next = head;
        // 断开当前节点原来的 next 指向，防止形成环
        head.next = null;

        // 返回新的头节点
        return newHead;
    }



}
